[求助]装箱问题

来源:百度知道 编辑:UC知道 时间:2024/05/22 04:09:07
有哪位高手能帮我写出下问题的程序:

有一批共n个集装箱要装上两艘载重量分别为c1和c2的轮船,其中集装箱i的总量为wi,且满足∑wi≤c1+c2,装箱问题要求确定,是否有一个合理的装载方案可将这n个集装箱装上这两艘轮船。设计该问题的回溯算法,并分析问题的复杂度。

装载问题:有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船,其中集装箱i的重量为wi,且∑wi<=c1+c2。要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有,找出一种装载方案。

#include<iostream>
using namespace std;
//------------------------------------------------
class Loading
{
friend float MaxLoading(float[],float,int);

public:
void Backtrack(int i);
int n;
int *x,*bestx;
float *w,c,cw,bestw,r;
};
//-------------------------
float Maxloading(float w1[],float c1,float c2,int n1,int bestx1[])
{
Loading k;
int j;
float MAXLoad;
k.x= new int [n1+1];
k.bestx=bestx1;
k.w = w1;
k.c = c1;
k.n = n1;
k.cw = 0;
k.bestw = 0;
k.r = 0;
for(int i=1;i<=n1;i++)
k.r+=w1[i];
k.Backtrack(1);
delete [] k.x;
cout<<"船1最优装载:"<<k.bestw<<endl;
MAXLoad=k.bestw;
for( j=1;j<=n1;j++)
{
if(k.bestx[j]==0)
{